/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.tests;

import java.util.Iterator;

import junit.framework.TestCase;

import java.util.LinkedList;
import mosdi.util.TreeNode;
import mosdi.util.iterators.PostOrderIterator;

public class PostOrderIteratorTest extends TestCase {
	
	private class TestNode implements TreeNode {
		int nr;
		private LinkedList<TestNode> children;
		TestNode(int nr) {
			this.nr=nr;
			children = new LinkedList<TestNode>();
		}
		public void addChild(TestNode child) {
			children.add(child);
		}
		public Iterator<TestNode> children() {
			return children.iterator();
		}
		public boolean hasChild() {
			return children.size()>0;
		}
	}
	
	private TestNode[] nodes;
	
	@Override
	protected void setUp() throws Exception {
		nodes = new TestNode[10];
		for (int i=0; i<10; ++i) nodes[i] = new TestNode(i);
		nodes[9].addChild(nodes[4]);
		nodes[9].addChild(nodes[5]);
		nodes[9].addChild(nodes[8]);
		nodes[4].addChild(nodes[3]);
		nodes[3].addChild(nodes[0]);
		nodes[3].addChild(nodes[1]);
		nodes[3].addChild(nodes[2]);
		nodes[8].addChild(nodes[6]);
		nodes[8].addChild(nodes[7]);
	}

	public void testIterator() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9]);
		assertEquals(0, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(1, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(2, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(3, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(4, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertEquals(5, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertEquals(6, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(7, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(8, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertEquals(9, iter.next().nr);
		assertEquals(0, iter.getDepth());
		assertFalse(iter.hasNext());
	}
	
	public void testMinDepth1() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],1,-1);
		assertEquals(0, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(1, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(2, iter.next().nr);
		assertEquals(3, iter.getDepth());
		assertEquals(3, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(4, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertEquals(5, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertEquals(6, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(7, iter.next().nr);
		assertEquals(2, iter.getDepth());
		assertEquals(8, iter.next().nr);
		assertEquals(1, iter.getDepth());
		assertFalse(iter.hasNext());
	}
	
	public void testMinDepth2() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],2,-1);
		assertEquals(0, iter.next().nr);
		assertEquals(1, iter.next().nr);
		assertEquals(2, iter.next().nr);
		assertEquals(3, iter.next().nr);
		assertEquals(6, iter.next().nr);
		assertEquals(7, iter.next().nr);
		assertFalse(iter.hasNext());
	}

	public void testMinDepth3() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],3,-1);
		assertEquals(0, iter.next().nr);
		assertEquals(1, iter.next().nr);
		assertEquals(2, iter.next().nr);
		assertFalse(iter.hasNext());
	}

	public void testMaxDepth1() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],-1,1);
		assertEquals(4, iter.next().nr);
		assertEquals(5, iter.next().nr);
		assertEquals(8, iter.next().nr);
		assertEquals(9, iter.next().nr);
		assertFalse(iter.hasNext());
	}

	public void testMaxDepth2() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],-1,2);
		assertEquals(3, iter.next().nr);
		assertEquals(4, iter.next().nr);
		assertEquals(5, iter.next().nr);
		assertEquals(6, iter.next().nr);
		assertEquals(7, iter.next().nr);
		assertEquals(8, iter.next().nr);
		assertEquals(9, iter.next().nr);
		assertFalse(iter.hasNext());
	}

	public void testMinMaxDepth1() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],1,2);
		assertEquals(3, iter.next().nr);
		assertEquals(4, iter.next().nr);
		assertEquals(5, iter.next().nr);
		assertEquals(6, iter.next().nr);
		assertEquals(7, iter.next().nr);
		assertEquals(8, iter.next().nr);
		assertFalse(iter.hasNext());
	}

	public void testMinMaxDepth2() {
		PostOrderIterator<TestNode> iter = new PostOrderIterator<TestNode>(nodes[9],2,2);
		assertEquals(3, iter.next().nr);
		assertEquals(6, iter.next().nr);
		assertEquals(7, iter.next().nr);
		assertFalse(iter.hasNext());
	}
}
